A fundamental problem in the field of data storage and communication is generating optimal or near optimal error-correcting codes (ECC) for data of a given block-length and transmission rate that can also be practically decoded. This problem is now nearly solved for small block-lengths, e.g., blocks of length N<100 bits, and for very large block-lengths, e.g., N>106 bits. However, error-correcting codes that are used in many applications, for example, wireless communication, typically have block-lengths in an intermediate range, around N=2000 bits. Generating optimal codes for these block-length remains a problem.
A large number of error-correcting codes are known for small block-lengths, many of which are known to be optimal, or near optimal. As long as the block-length is small enough, these ECC can be decoded practically and optimally using maximum-likelihood decoders.
The problem of finding optimal codes for very large block-lengths has been essentially solved by parity-check codes defined by generalized parity check matrices. These types of codes were first described by R. G. Gallager, in “Low-density parity check codes,” Vol.21, Research Monograph Series, MIT Press, 1963, but were not properly appreciated until recently. More recently, improved codes defined by sparse generalized parity check matrices have been described, such as turbocodes, irregular low-density parity check (LDPC) codes, Kanter-Saad codes, repeat-accumulate codes, and irregular repeat-accumulate codes.
These improved codes have three particularly noteworthy advantages. First, the codes can be decoded efficiently using belief propagation (BP) iterative decoding. Second, the performance of these codes can often be theoretically analyzed using a density evolution method, in an infinite-block-length limit. Third, by using a density evolution method, it can be demonstrated that these codes are nearly optimal codes. In the infinite-block-length limit, BP decoding of these codes decodes all data blocks that have a noise level below some threshold level, and that threshold level is often not far from the Shannon limit.
The preferred prior art way for generating improved codes has been to optimize codes for the infinite block-length limit using density evolution, and hope that a scaled-down version still results in a near optimal code. The problem with this method is that for N<104, at least, the block-length is still noticeably far from the infinite-block-length limit. In particular, many decoding failures are found at noise levels far below the threshold level predicted by infinite block-length calculations. Furthermore, there may not necessarily even exist a way to scale down the codes derived from the density evolution method.
For example, the best known irregular LDPC codes, at a given rate in the N→∞ limit, often have variable nodes that should participate in hundreds or even thousands of parity checks, which makes no sense when the overall number of parity checks is 100 or less.
Density Evolution Method for a Binary Erasure Channel (BEC)
The density evolution method is simple for a binary erasure channel. A binary erasure channel is a binary input channel with three output symbols: 0, 1, and an erasure, which can be represented by a question mark “?.” Because this method is important background information for the method according to the invention, it is distinguished in greater detail.
Parity Check Codes
Linear block binary error-correcting codes can be defined in terms of a parity check matrix. In a parity check matrix A, the columns represent transmitted variable bits, and the rows define linear constraints or checks between the variable bits. More specifically, the matrix A defines a set of valid vectors or codewords z, such that each component of z is either 0 or 1, andAz=0  , (1)where all multiplication and addition are modulo 2.
If the parity check matrix has N columns and N-k rows, then the parity check defines an error correcting code of block-length N and transmission rate k/N, unless some of the rows are linearly dependent, in which case some of the parity checks are redundant, and the code actually has a higher transmission rate.
As shown in FIG. 1, there is a corresponding Tanner graph for each parity check matrix, see R. M. Tanner, “A recursive method to low complexity codes,” IEEE Trans. Info. Theory, IT-27, pages 533-547, 1981. The Tanner graph 100 is a bipartite graph with two types of nodes: variable nodes i denoted by circles, and check nodes a denoted by squares. In the Tanner graph, each variable node is connected to the check node participating in the check for the variable node i.
For example, the parity check matrix                     A        =                  (                                                    1                                            1                                            0                                            1                                            0                                            0                                                                    1                                            0                                            1                                            0                                            1                                            0                                                                    0                                            1                                            1                                            0                                            0                                            1                                              )                                    (        2        )            is represented by the bipartite Tanner graph shown in FIG. 1.
It should be understood, that in practical applications the graphs typically include thousands of nodes connected in any number of different ways, and containing many cycles. Analyzing such graphs to determine optimal configurations is difficult.
Error-correcting codes defined by parity check matrices are linear. This means that each codeword is a linear combination of other codewords. In a check matrix, there are 2k possible codewords, each of length N. For the example given the above, the codewords are 000000, 001011, 010110, 011101, 100110, 101101, 110011, 111000. Because of the linearity property, any of the codewords are representative. For the purposes of analyzing a code, it is therefore normally assumed that the all-zeros codeword is transmitted.
Belief Propagation Decoding in the BEC
An input bit passes through the binary erasure channel as an erasure with probability x and is received correctly with probability 1−x. It is important to note that the BEC never flips bits from 0 to 1, or vice versa. If all-zeros codewords are transmitted, the received word must consist entirely of zeros and erasures.
The receiver uses a belief propagation (BP) decoder to decode the input bits by passing discrete messages between the nodes of the Tanner graph. A message mia is sent from each variable node i to each check node a connected to it. The message represents the state of the variable node i. In general, the message can be in one of three states: 1, 0, or ?, but because the all-zeros codeword is always transmitted, the possibility that mia has value 1 can be ignored.
Similarly, there is a message mai sent from each check node a to all the variable nodes i connected to the check node. These messages are interpreted as directives from the check node a to the variable node i about what state the variable node should be in. This message is based on the states of the other variable nodes connected to the check node. The check-to-variable messages can, in principle, take on the values 0, 1, or ?, but again only the two messages 0 and ? are relevant when the all-zeros codeword is transmitted.
In the BP decoding process for the BEC, a message mia from a variable node i to a check node a is equal to a non-erasure received message because such messages are always correct in the BEC, or to an erasure when all incoming messages are erasures. A message mai from a check node a to a variable node i is an erasure when any incoming message from another node participating in the check is an erasure; otherwise it takes on the value of the binary sum of all incoming messages from other nodes participating in the check.
BP decoding is iterative. The messages are initialized so that all variable nodes that are not erased by the channel send out messages equal to the corresponding received bit, and all other messages are initially erasures. Iterating the BP message process converges eventually to stationary messages because convergence of BP decoding is guaranteed for the particularly simple BEC, though not for other channels. The final decoded value of any erased variable node is just the value of any non-erasure message coming into that node, unless there is no incoming non-erasure message. In this case, the BP decoding process terminates and fails to decode the particular variable node.
Density Evolution
The average probability of failure for BP decoding over many blocks is now considered. A real number pia, which represents the probability that the message mia is an erasure, is associated with each message mia. Similarly, a real number qai, which represents the probability that the message mai is an erasure, is associated with each message mai. In the density evolution method, probabilities pia and qai are determined in a way that is exact, as long as the Tanner graph representing the error-correcting code has no cycles.
The equation for pia is                                           p                          i              ⁢                                                           ⁢              a                                =                      x            ⁢                                          ∏                                  b                  ∈                                                            N                      ⁡                                              (                        i                        )                                                              ⁢                    \                    ⁢                    a                                                              ⁢                              q                                  b                  ⁢                                                                           ⁢                  i                                                                    ,                            (        3        )            where b∈N(i)\a represents all check nodes directly connected to a neighboring variable node i, except for check node a. This equation can be derived from the fact that for a message mia to be an erasure, the variable node i must be erased in transmission, and all incoming messages from other check nodes are erasures as well. Of course, if the incoming messages are correlated, then this equation is not correct. However, in a Tanner graph with no cycles, each incoming message is independent of all other messages.
Similarly, the equation                               q                      a            ⁢                                                   ⁢            i                          =                  1          -                                    ∏                              j                ∈                                                      N                    ⁡                                          (                      a                      )                                                        ⁢                  \                  ⁢                  i                                                      ⁢                          (                              1                -                                  p                                      j                    ⁢                                                                                   ⁢                    a                                                              )                                                          (        4        )            can be derived from the fact that a message mai can only be in a 0 or 1 state when all incoming messages are in either a zero or one state.
The density evolution equations (3) and (4) can be solved by iteration. A good initialization is pia=x for all messages from variable nodes to check nodes and qai=0 for all messages from check nodes to variable nodes, as long as the iteration begins with the mai messages. The BEC density evolution equations ultimately converge. This can be guaranteed for codes defined in graphs without cycles. It is possible to determine bi, which is the probability of a failure to decode at variable node i, from the formula                               b                      i            ⁢                                                                 =                  x          ⁢                                    ∏                              a                ∈                                  N                  ⁡                                      (                    i                    )                                                                        ⁢                                          q                                  a                  ⁢                                                                           ⁢                  i                                            .                                                          (        5        )            Exact Solution of a Small Code
As stated above, the density evolution equations (3, 4, and 5) are exact when the code has a Tanner graph representation without cycles.
Consider the error-correcting code defined by a parity check matrix                     A        =                  (                                                    1                                            1                                            0                                            0                                                                    0                                            1                                            1                                            1                                              )                                    (        6        )            and represented by a corresponding Tanner graph shown in FIG. 2. This code has four codewords: 0000, 0011, 1101, and 1110. If the 0000 message is transmitted, then there are sixteen possible received messages: 0000, 000?, 00?0, 00??, 0?00, and so on. The probability of receiving a message with ne erasures is xne(1−x)4-ne. Messages might be partially or completely decoded by the BP decoder; for example the received message ?00? is fully decoded to 0000, but the message 0??? is only partially decoded to 00??, because there is not enough information to determine whether the transmitted codeword was actually 0000 or 0011.
It is easy to determine the exact probability that a given bit remains an erasure after decoding by summing over the sixteen possible received messages weighted by their probabilities. For example, the first bit is only decoded as an erasure when one of the following messages is received: ???0, ??0?, or ????, so the correct probability that the first bit is not decoded is 2x3(1−x)+x4=2x3−x4.
If the focus is on the last bit, then the message is decoded, unless one of the following messages is sent: 00??, 0???, ?0??, ??0? or ????. Therefore, the overall probability that the fourth bit is not decoded is x2(1−x)2+3x3(1−x)+x4=x2+x3−x4. In the density evolution method, the values for the following variables:p11, p21, p22, p32, p42, q11, q12, q22, q23, q24, b1, b2, b3, b4are determined by equationsp11=x  (7)p21=xq22  (8)p22=xq12  (9)p32=x  (10)p42=x  (11a)q11=p21  (11b)q12=p11  (12)q22=1−(1−p32)(1−p42)  (13)q23=1−(1−p22)(1−p42)  (14)q24=1−((1−p32)(1−p22))  (15)andb1=xq11  (16)b2=xq12q22  (17)b3=xq23  (18)b4=xq24.  (19)Solving these equations yieldsp11=x  (20) p21=2x2−x3  (21)p22=x2  (22)p32=x  (23)p42=x  (24)p11=2x2−x3  (25)andq12=x  (26)q22=2x−x2  (27)q23=x+x2−x3  (28)q24=x+x2−x3  (29)andb1=2x3−x4  (30)b2=2x3−x4  (31)b3=x2+x3−x4  (32)b4=x2+x3−x4  (33)
Examining the results for b1 and b4 indicates that the density evolution solution agrees exactly with the direct approach for this code.
The Large Block-length Limit
If all local neighborhoods in the Tanner graph are identical, the density evolution equations can be simplified. For example, if each variable node i is connected to dv check nodes, and each check node a is connected to dc variable nodes, then all the pia are equal to the same value p, all the qai are equal to the same value q, and all the bi are equal to the same value b. Then,p=xqdv−1  (34)q=1−(1−p)dc−1  (35)andb=xqdv  (36)which are the density evolution equations for (dv, dc) regular Gallager codes, valid in the N→∞ limit. A regular Gallager code is a sparse random parity check matrix characterized by the restriction that each row has exactly dc ones in it, and each column contains exactly dv ones.
The intuitive reason that these equations are valid, in the infinite block-length limit, is that as N→∞, the size of typical cycles in the Tanner graph of a regular Gallager code go to infinity, so all incoming messages to a node are independent, and a regular Gallager code behaves as a code defined on a graph without cycles. Solving equations (34 and 35) for specific values of dv and dc yields a solution that is p=q=b=0, below a critical erasure limit of xc. This means that decoding is perfect. Above xc, b has a non-zero solution, which correspond to decoding failures. The value xc is easy to determine numerically. For example, if dv=3 and dc=5, then xc≈0.51757.
These density evolution calculations can be generalized to irregular Gallager codes, or other codes like irregular repeat-accumulate codes which have a finite number of different classes of nodes with different neighborhoods. In this generalization, one can derive a system of equations, typically with one equation for the messages leaving each class of node. By solving the system of equations, one can again find a critical threshold xc, below which decoding is perfect. Such codes can thus be optimized, in the N→∞ limit, by finding the code that has maximal noise threshold xc.
Unfortunately, the density evolution method is erroneous for codes with finite block-lengths. One might think that it is possible to solve equations (3 and 4) for any finite code, and hope that ignoring the presence of cycles is not too important a mistake. However, this does not work out, as can be seen by considering regular Gallager codes. Equations (3, 4, and 5) for a finite block-length regular Gallager code have exactly the same solutions as one would find in the infinite-block-length limit, so one would not predict any finite-size effects. However, it is known that the real performance of finite-block-length regular Gallager codes is considerably worse than that predicted by such a naive method.
Therefore, there is a need for a method to correctly evaluate finite length error-correcting codes that do not suffer from the problems of the prior art methods.